package NiuKe.JianZhiOffer;

import java.util.*;

/**
 * 描述
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜索树）
 * 示例1
 * 输入：
 * [4,8,6,12,16,14,10]
 * 复制
 * 返回值：
 * true
 */
public class JZ23 {
    public static void main(String[] args) {
        int a[] ={7,4,9,3,8,11,12,10};
        JZ23 jz = new JZ23();
        System.out.println(jz.VerifySquenceOfBST(a));

        /*ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(8);
        int arr[] = jz.change(list);
        for (int i = 0 ; i < arr.length ; i++){
            System.out.println(arr[i]);
        }*/
    }
    public boolean VerifySquenceOfBST(int [] sequence) {

        if(sequence.length == 1)return true;
        if(sequence.length == 0)return false;
        JZ23 jz = new JZ23();
        int length = sequence.length;
        int root = sequence[length-1];
        ArrayList<Integer> left = new ArrayList<Integer>();
        ArrayList<Integer> right = new ArrayList<Integer>();

        boolean flag = false;
        for (int i = 0 ; i < length ; i++){
            if(!flag && sequence[i] > root ){
                flag = true;
            }
            if(flag && sequence[i] < root ){
                System.out.println("///0"+sequence[i]);
                return false;
            }

            if ( sequence[i] < root ){
                left.add(sequence[i]);
            }

            if ( sequence[i] > root && i < length-1){
                right.add(sequence[i]);
            }

        }
        int arrLeft[] = jz.change(left);
        int arrRight[] = jz.change(right);

        boolean result = false;
        if (arrLeft == null || arrLeft.length < 2){
            result = true;
        }else if ( VerifySquenceOfBST( arrLeft ) ){
            result = true;
        }

        if(result && (arrRight == null || arrRight.length <2) ){
            result = true;
        }else if ( result && !VerifySquenceOfBST( arrRight ) ){
            result = false;
        }
        return  result;
    }

    public int[] change(ArrayList list){
        int length = list.size();
        int array[] = new int[length];
        for (int i = 0; i < length; i++){
            array[i] =(int)list.get(i);
        }
        return array;
    }
}
